package com.ljy.my_study.动态规划.合并石子;
/** 
* @author James
* @date 2018年6月14日 
*/
public class TestMain {
	/**
	 * 在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。
	 * 规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
	 * 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性
	 * 分析：比如有3堆,石子个数分别为1,2,3。那么先合并1，2堆，再与第3堆合并的得分是(1+2)+(3+3)=9。
	 * 先合并2，3堆，再与第1堆合并的得分是(2+3)+(5+1)=11。
	 * f[i,j]表示从第i个起接下来j个合并的的最大值d[i,j]表示第i到第j个的价值和，
	 * 则f[i,j]=max{[i,k]+f[i+k,j-k]+d[i,j]}，f[i,1]=0。
	 * 最小分跟huffman最小生成树是同一个原理，算法就是最小生成树算法，
	 * 把权最小的先合并，并把和做为新堆的权，重复合并，最后生成一棵树，根部的权就是得的分。最大分也应该类似。
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr=new int[]{1,2,3};
//		Stack stack=setStackList(arr);
//		Stack nowStack=stack;
//		int firstScore=0;
//		int secondScore=0;
//		int maxSum=0;
//		int j=0;
//		for(int i=0;i<arr.length;i++) {
//			firstScore=nowStack.lastStack.value;
//			secondScore=nowStack.value;
//			if(maxSum<(firstScore+secondScore)) {
//				maxSum=firstScore+secondScore;
//				j=i;
//			}
//		}
//		System.out.println(stack.size());
		maxScore(arr);
	}
	
	public static int maxScore(int[] arr) {
		if(arr.length==0) {
			return 0;
		}
		if(arr.length==1) {
			return arr[0];
		}
		if(arr.length==2) {
			return arr[0]+arr[1];
		}
		Stack stack=setStackList(arr);
		
		int score=0;
		int stackNum=stack.value;
		
		
		Stack nowStack=stack;
		int j=1;
		for(int i=0;i<arr.length;i++) {
			if(j==arr.length) {
				return 0;
			}
			Stack nextStack=nowStack.nextStack;
			score=score+stackNum+nextStack.value;
			stackNum+=nextStack.value;
			nowStack=nextStack;
			System.out.println("score:"+score+",stackNum:"+stackNum+",j:"+j);
			j++;
		}
//		int maxScore=maxScore
		return 0;
	}
	
	public static Stack setStackList(int[] arr) {
		Stack stack=new Stack();
		stack.value=arr[0];
		Stack nowStack=stack;
		
		for(int i=1;i<arr.length;i++) {
			Stack newStack=new Stack();
			newStack.value=arr[i];
			newStack.lastStack=nowStack;
			
			nowStack.nextStack=newStack;
			
			nowStack=newStack;
		}
		nowStack.nextStack=stack;
		stack.lastStack=nowStack;
		return stack;
	}
	
	static class Stack {
		int value;
		Stack lastStack;
		Stack nextStack;
		
		@Override
		public String toString() {
			return "Stack [value=" + value + "]";
		}
		
		public int size() {
			int count=1;
			Stack nextStack=this.nextStack;
			while(nextStack!=null&&nextStack!=this) {
				count++;
				nextStack=nextStack.nextStack;
			}
			return count;
		}
	}
}
